/*
98 验证二叉搜索树

思路：BST的中序遍历(左中右)是升序的
 */

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function (root) {
  if (!root) {
    return false
  }
  const stack = []
  let prev
  while (stack.length || root) {
    if (root) {
      stack.push(root)
      root = root.left
    } else {
      root = stack.pop()
      if (prev && prev > root.val) {
        return false
      } else {
        prev = root.val
      }
      root = root.right
    }
  }
  return true
}
